home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / zoo21src.zoo / encode.c < prev    next >
C/C++ Source or Header  |  1991-07-24  |  8KB  |  332 lines
  1. /*$Source: g:/newzoo\RCS\encode.c,v $*/
  2. /*$Id: encode.c,v 1.4 1991/07/24 23:47:04 bjsjr Rel $*/
  3.  
  4. /*
  5. Adapted from "ar" archiver written by Haruhiko Okumura.
  6. */
  7.  
  8. #include "options.h"
  9. #include "zoo.h"
  10. #include "ar.h"
  11. #include "lzh.h"
  12.  
  13. extern void prterror PARMS((int, char *, ...));
  14. extern char *out_buf_adr;
  15.  
  16. #include <assert.h>
  17.  
  18. #ifdef ANSI_HDRS
  19. # include <stdlib.h>
  20. # include <string.h>
  21. #endif
  22.  
  23. #include "errors.i"
  24.  
  25. FILE *lzh_infile;
  26. FILE *lzh_outfile;
  27.  
  28. /*
  29. sliding dictionary with percolating update
  30. */
  31.  
  32. #define PERCOLATE  1
  33. #define NIL        0
  34. #define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)
  35.  
  36. typedef short node;
  37.  
  38. static uchar *text, *childcount;
  39. static node pos, matchpos, avail,
  40.     *position, *parent, *prev, *next = NULL;
  41. static int remainder, matchlen;
  42.  
  43. #if MAXMATCH <= (UCHAR_MAX + 1)
  44.     static uchar *level;
  45. # define T_LEVEL  uchar *
  46. #else
  47.     static ushort *level;
  48. # define T_LEVEL  ushort *
  49. #endif
  50.  
  51. static void allocate_memory()
  52. {
  53.     if (next != NULL) return;
  54.     /* text = (uchar *) malloc(DICSIZ * 2 + MAXMATCH); */
  55.     text = (uchar *) out_buf_adr; /* reuse I/O buffer used elsewhere */
  56.     level      = (T_LEVEL) malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
  57.     childcount = (uchar *)malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
  58. #ifdef PERCOLATE
  59.       position = (node *) malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
  60. #else
  61.       position = (node *) malloc(DICSIZ * sizeof(*position));
  62. #endif
  63.     parent     = (node *) malloc(DICSIZ * 2 * sizeof(*parent));
  64.     prev       = (node *) malloc(DICSIZ * 2 * sizeof(*prev));
  65.     next       = (node *) malloc((MAX_HASH_VAL + 1) * sizeof(*next));
  66.     if (next == NULL) prterror('f', no_memory);
  67. }
  68.  
  69. static void init_slide()
  70. {
  71.     node i;
  72.  
  73.     for (i = DICSIZ; i <= DICSIZ + UCHAR_MAX; i++) {
  74.         level[i] = 1;
  75. #ifdef PERCOLATE
  76.             position[i] = NIL;  /* sentinel */
  77. #endif
  78.     }
  79.     for (i = DICSIZ; i < DICSIZ * 2; i++) parent[i] = NIL;
  80.     avail = 1;
  81.     for (i = 1; i < DICSIZ - 1; i++) next[i] = i + 1;
  82.     next[DICSIZ - 1] = NIL;
  83.     for (i = DICSIZ * 2; i <= MAX_HASH_VAL; i++) next[i] = NIL;
  84. }
  85.  
  86. #define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)
  87.  
  88. #ifdef __GNUC__
  89. inline
  90. #endif
  91. static node child(q, c)
  92. node q;
  93. uchar c;
  94.     /* q's child for character c (NIL if not found) */
  95. {
  96.     node r;
  97.  
  98.     r = next[HASH(q, c)];
  99.     parent[NIL] = q;  /* sentinel */
  100.     while (parent[r] != q) r = next[r];
  101.     return r;
  102. }
  103.  
  104. #ifdef __GNUC__
  105. inline
  106. #endif
  107. static void makechild(q, c, r)
  108. node q;
  109. uchar c;
  110. node r;
  111.     /* Let r be q's child for character c. */
  112. {
  113.     node h, t;
  114.  
  115.     h = HASH(q, c);
  116.     t = next[h];  next[h] = r;  next[r] = t;
  117.     prev[t] = r;  prev[r] = h;
  118.     parent[r] = q;  childcount[q]++;
  119. }
  120.  
  121. #ifdef __GNUC__
  122. inline
  123. #endif
  124. void split(old)
  125. node old;
  126. {
  127.     node new, t;
  128.  
  129.     new = avail;  avail = next[new];  childcount[new] = 0;
  130.     t = prev[old];  prev[new] = t;  next[t] = new;
  131.     t = next[old];  next[new] = t;  prev[t] = new;
  132.     parent[new] = parent[old];
  133.     level[new] = matchlen;
  134.     position[new] = pos;
  135.     makechild(new, text[matchpos + matchlen], old);
  136.     makechild(new, text[pos + matchlen], pos);
  137. }
  138.  
  139. static void insert_node()
  140. {
  141.     node q, r, j, t;
  142.     uchar c, *t1, *t2;
  143.  
  144.     if (matchlen >= 4) {
  145.         matchlen--;
  146.         r = (matchpos + 1) | DICSIZ;
  147.         while ((q = parent[r]) == NIL) r = next[r];
  148.         while (level[q] >= matchlen) {
  149.             r = q;  q = parent[q];
  150.         }
  151. #ifdef PERCOLATE
  152.             t = q;
  153.             while (position[t] < 0) {
  154.                 position[t] = pos;  t = parent[t];
  155.             }
  156.             if (t < DICSIZ) position[t] = pos | PERC_FLAG;
  157. #else
  158.             t = q;
  159.             while (t < DICSIZ) {
  160.                 position[t] = pos;  t = parent[t];
  161.             }
  162. #endif
  163.     } else {
  164.         q = text[pos] + DICSIZ;  c = text[pos + 1];
  165.         if ((r = child(q, c)) == NIL) {
  166.             makechild(q, c, pos);  matchlen = 1;
  167.             return;
  168.         }
  169.         matchlen = 2;
  170.     }
  171.     for ( ; ; ) {
  172.         if (r >= DICSIZ) {
  173.             j = MAXMATCH;  matchpos = r;
  174.         } else {
  175.             j = level[r];
  176.             matchpos = position[r] & ~PERC_FLAG;
  177.         }
  178.         if (matchpos >= pos) matchpos -= DICSIZ;
  179.         t1 = &text[pos + matchlen];  t2 = &text[matchpos + matchlen];
  180.         while (matchlen < j) {
  181.             if (*t1 != *t2) {  split(r);  return;  }
  182.             matchlen++;  t1++;  t2++;
  183.         }
  184.         if (matchlen >= MAXMATCH) break;
  185.         position[r] = pos;
  186.         q = r;
  187.         if ((r = child(q, *t1)) == NIL) {
  188.             makechild(q, *t1, pos);  return;
  189.         }
  190.         matchlen++;
  191.     }
  192.     t = prev[r];  prev[pos] = t;  next[t] = pos;
  193.     t = next[r];  next[pos] = t;  prev[t] = pos;
  194.     parent[pos] = q;  parent[r] = NIL;
  195.     next[r] = pos;  /* special use of next[] */
  196. }
  197.  
  198. #ifdef __GNUC__
  199. inline
  200. #endif
  201. static void delete_node()
  202. {
  203. #ifdef PERCOLATE
  204.         node q, r, s, t, u;
  205. #else
  206.         node r, s, t, u;
  207. #endif
  208.  
  209.     if (parent[pos] == NIL) return;
  210.     r = prev[pos];  s = next[pos];
  211.     next[r] = s;  prev[s] = r;
  212.     r = parent[pos];  parent[pos] = NIL;
  213.     if (r >= DICSIZ || --childcount[r] > 1) return;
  214. #ifdef PERCOLATE
  215.         t = position[r] & ~PERC_FLAG;
  216. #else
  217.         t = position[r];
  218. #endif
  219.     if (t >= pos) t -= DICSIZ;
  220. #ifdef PERCOLATE
  221.         s = t;  q = parent[r];
  222.         while ((u = position[q]) & PERC_FLAG) {
  223.             u &= ~PERC_FLAG;  if (u >= pos) u -= DICSIZ;
  224.             if (u > s) s = u;
  225.             position[q] = (s | DICSIZ);  q = parent[q];
  226.         }
  227.         if (q < DICSIZ) {
  228.             if (u >= pos) u -= DICSIZ;
  229.             if (u > s) s = u;
  230.             position[q] = s | DICSIZ | PERC_FLAG;
  231.         }
  232. #endif
  233.     s = child(r, text[t + level[r]]);
  234.     t = prev[s];  u = next[s];
  235.     next[t] = u;  prev[u] = t;
  236.     t = prev[r];  next[t] = s;  prev[s] = t;
  237.     t = next[r];  prev[t] = s;  next[s] = t;
  238.     parent[s] = parent[r];  parent[r] = NIL;
  239.     next[r] = avail;  avail = r;
  240. }
  241.  
  242. #ifdef __GNUC__
  243. inline
  244. #endif
  245. static void get_next_match()
  246. {
  247.     int n;
  248.  
  249.     remainder--;
  250.     if (++pos == DICSIZ * 2) {
  251. #ifdef CHECK_BREAK
  252.         check_break();
  253. #endif
  254.         (void) MOVE_LEFT((char *) &text[0], (char *) &text[DICSIZ], DICSIZ + MAXMATCH);
  255.         n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, lzh_infile);
  256.         remainder += n;  pos = DICSIZ;  
  257. #ifdef SHOW_DOTS
  258.         (void) putc('.', stderr);
  259.         (void) fflush(stderr);
  260. #endif
  261.     }
  262.     delete_node();  insert_node();
  263. }
  264.  
  265. /* read from infile, compress, write to outfile */
  266. void encode(infile, outfile)
  267. FILE *infile;
  268. FILE *outfile;
  269. {
  270.     int lastmatchlen;
  271.     node lastmatchpos;
  272.  
  273.     /* make input/output files visible to other functions */
  274.     lzh_infile = infile;
  275.     lzh_outfile = outfile;
  276.  
  277.     allocate_memory();  init_slide();  huf_encode_start();
  278.     remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, lzh_infile);
  279. #ifdef SHOW_DOTS
  280.     (void) putc('.', stderr);
  281.     (void) fflush(stderr);
  282. #endif
  283.     matchlen = 0;
  284.     pos = DICSIZ;  insert_node();
  285.     if (matchlen > remainder) matchlen = remainder;
  286.     while (remainder > 0 && ! unpackable) {
  287.         lastmatchlen = matchlen;  lastmatchpos = matchpos;
  288.         get_next_match();
  289.         if (matchlen > remainder) matchlen = remainder;
  290.         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
  291. #if 0
  292.             d1log("%c", text[pos-1]);
  293. #endif
  294.             output(text[pos - 1], 0);
  295.         } else {
  296. #if 0
  297.         (void) putc('.', stderr); (void) fflush(stderr);
  298. #endif
  299.  
  300. #if 0
  301.             {
  302.                 int i; 
  303.                 d1log("\nlastmatchlen=%d, pos=%d, lastmatchpos=%d",
  304.                             lastmatchlen, pos, lastmatchpos);
  305.                 d1log("\n[%d: ", (int) lastmatchlen);
  306.                 for (i = 0;  i < lastmatchlen;  i++)
  307.                     d1log("%c", text[lastmatchpos + i]);
  308.                 d1log("]\n");
  309.             }
  310. #endif
  311.  
  312.             output((uint) (lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD)),
  313.                    (uint) ((pos - lastmatchpos - 2) & (DICSIZ - 1)));
  314.             while (--lastmatchlen > 0) get_next_match();
  315.             if (matchlen > remainder) matchlen = remainder;
  316.         }
  317.     }
  318.     huf_encode_end();
  319. }
  320.  
  321. #ifdef NEED_MEMMOVE
  322. /* like memmove, but for moving stuff LEFT (downwards in memory) only!! */
  323. void move_left(dest, src, len)
  324. char *dest;
  325. char *src;
  326. int len;
  327. {
  328.     while (len-- > 0)
  329.         *dest++ = *src++;
  330. }
  331. #endif /* NEED_MEMMOVE */
  332.